package top.humbleyuan.leet;

import org.junit.Test;
import top.humbleyuan.leet.datastructure.tree.TreeNode;

import java.util.*;


/**
 * @Author YHH
 * @Date 2019/9/5 19:17
 * @Des
 */
public class Dynamic {

    /**
     * 10.正则匹配
     *
     * if p[j](包含.) == s[i]
     *      相当于同时添加一个相同字母，即dp[i][j] == dp[i-1][j-1]
     * if p[j] == "*"
     *      if p[j-1] == s[i]   //说明可匹配
     *          1.*表示0个删除p[j-1],即dp[i][j] == dp[i][j-2]
     *          2.*表示一个，即dp[i][j] == dp[i][j-1]
     *          3.因为s[i] = p[j-1] && p[j] == "*",所以dp[i][j] == dp[i-1][j]
     *              加了个s[i],相当于给p串多加了个p[j-1]
     *       else
     *          dp[i][j] = dp[i][j-2] 即*只能表示0个，去掉两个字符
     *
     */

    @Test
    public void isMatch() {
        String s = "";
        String p = "a*";

        /**
         dp:
         dp[i][j]表示Pi串和Sj串是否匹配
         状态转移：
         1. p[i] = s[j]  =>  dp[i][j] = dp[i - 1][j - 1]
         2. p[i] != s[j] :
         2.1 p[i]是字母  =>  dp[i][j] = false
         2.2 p[i] = '*':
         2.2.1 p[i - 1] != s[j]  表示*是0个 => dp[i][j] = dp[i - 2][j]
         2.2.2 p[i - 1] = s[j] || p[i - 1] == '.':
         a. dp[i][j - 2] 表示*是0个
         b. dp[i][j - 1] 表示*是1个
         c. dp[i - 1][j]表示*是多个
         => a or b or c
         2.3 p[i] = '.'  =>  dp[i][j] = dp[i - 1][j - 1]

         **/
        if(p == null || p == "") {
            if(s == null || s == "") {
                System.out.println(true);
                return ;
            }
            System.out.println(false);
            return ;
        }

        if(s == null || s == "") {
            System.out.println(false);
            return ;
        }



        boolean[][] dp = new boolean[p.length() + 1][s.length() + 1];
        dp[0][0] = true;

        for (int i = 1; i < p.length(); i++) {   /*为了消除a*这种与空串的匹配，比如s是空，a*或者a*b*都是满足条件的，执行这个                                                    循环就可以得到满足条件的情况，并设为true*/
            // 这种指*表示0个
            if (p.charAt(i) == '*') {
                dp[i + 1][0] = dp[i - 1][0];
            }
        }

        for(int i = 0;i < p.length();i++) {
            for(int j = 0;j < s.length();j++) {
                if(p.charAt(i) == s.charAt(j) || p.charAt(i) == '.') {
                    dp[i + 1][j + 1] = dp[i][j];
                    continue;
                }

                if(p.charAt(i) == '*'  && i > 0) {
                    if(p.charAt(i - 1) == s.charAt(j) || p.charAt(i - 1) == '.'){
                        dp[i + 1][j + 1] = dp[i - 1][j + 1] || dp[i][j + 1] || dp[i + 1][j];
                    } else{
                        dp[i + 1][j + 1] = dp[i - 1][j + 1];
                    }
                    continue;
                }

            }
        }


        System.out.println(dp[p.length()][s.length()]);
    }

    /**
     * 121.买卖股票
     */
    @Test
    public void dynamic121() {
        int[] prices = {7,1,5,3,6,4};
        /*
          谷峰思想
          一次遍历记录下前面的最小值，遍历过程中只需将当前值与前面最小值求差取最大就行
         */
        int minPrice = prices[0];
        int maxProfit = 0;

        for (int i = 1;i < prices.length;i++) {
            minPrice = prices[i] > minPrice ? minPrice : prices[i];
            maxProfit = prices[i] - minPrice > maxProfit ? prices[i] - minPrice : maxProfit;
        }
        System.out.println(maxProfit);
    }

    /**
     * 不同路径
     * d[i][j]表示到(i,j)这个点有多少条路径:
     * d[0][0] = 1
     * d[i][j] = d[i-1][j] + d[i][j-1] (i<=m-1,j<=n-1)
     *
     */
    @Test
    public void dynamic62() {
        // 网格大小
        int m = 7,n = 3;
        int[][] d = new int[n][m];

        d[0][0] = 1;
        for (int i = 0;i < n;i++) {
            for(int j = 0; j < m;j++) {
                if(i == 0 && j == 0)
                    continue;
                d[i][j] = (i==0 ? 0 : d[i-1][j]) + (j==0 ? 0 : d[i][j-1]);
            }
        }

        System.out.println("共有：" + d[n-1][m-1] + "条路径");
    }

    /**
     * 用一个一维数组:
     * 一行一行求：
     * 1.因为二维数组的话第一行和第一列都为1，可先设为一
     * 2.从第二行开始，因为cur记录着上一行的数据，那么现在这一行的cur[j] = cur[j](上一个) + cur[j-1](前一个已经变成新一行的数据)
     */
    @Test
    public void dynamic62_2() {
        // 网格大小
        int m = 7,n = 3;

        int[] d = new int[m];
        Arrays.fill(d,1);
        for(int i = 1;i < n;i++) {
            for (int j = 1;j < m;j++) {
                d[j] = d[j] + d[j-1];
            }
        }
        System.out.println(d[m-1]);
    }

    /**
     * 有障碍不同路径
     */
    @Test
    public void dynamic63() {
        int[][] mn = new int[][]{{0,0,0,1},{0,0,1,0},{0,0,0,0}};

        int[] d = new int[mn[0].length];
        // 先确定第一行
        for(int i = 0;i < mn[0].length;i++) {
            if(mn[0][i] == 1) {
                Arrays.fill(d,i,mn[0].length,0);
                break;
            }
            d[i] = 1;
        }

        // 从第二行开始
        for(int i = 1;i < mn.length;i++) {
            for(int j = 0;j < mn[i].length;j++) {
                if (j > 0 && (d[j] == 0 && d[j-1] == 0))
                    break;
                d[j] = mn[i][j] == 1 ? 0 : (j == 0 ? 0 : d[j-1]) + d[j];
            }
        }

        System.out.println(d[mn[0].length-1]);
    }

    /**
     * 解码
     * 注：考虑"10","01"不同情况
     * 状态：d[i]表示到第i个字符为止有多少种方法
     * d[0] = 1,d[1] = s(0,1) > 26 ? 1 : 2
     * d[i] = d[i-1] + ( s(i-1,i) > 26 ? 0 : d[i-2])
     * 如果大于26，则方法数没有增加；
     * 若小于26：
     *      分开：d[i-1]种
     *      合并：d[i-2]种
     */
    @Test
    public void dynamic91() {

        String s = "100";

        // 空串或0在开头
        if(s == null || s.length() == 0 || s.charAt(0) == '0') {
            System.out.println("有0种");
            return;
        }

        String newStr = "";
        int begin = 0;
        // 遍历一遍,检验将‘x0’形式的子串去掉
        for(int j = 1;j < s.length();j++) {
            if(s.charAt(j) == '0') {
                if(s.charAt(j-1) > '2' || s.charAt(j-1) == '0') {
                    System.out.println("有0种");
                    return;
                }
                else {
                    newStr += s.substring(begin,j-1);
                    begin = j+1;
                }
            }

        }
        newStr += s.substring(begin,s.length());
        int count = cal(newStr);
        System.out.println("共有"+ count + "种");
    }

    /**
     * 使用一次循环
     */
    @Test
    public void dynamic91_2() {
        String s = "227";

        // 空串或0在开头
        if(s == null || s.length() == 0 || s.charAt(0) == '0' ) {
            System.out.println("有0种");
            return;
        }
        if(s.length() == 1) {
            System.out.println("有1种");
            return;
        }
        if(s.charAt(1) == '0' && s.charAt(0) > '2' ) {
            System.out.println("有0种");
            return;
        }

        int[] d = new int[s.length()];
        d[0] = 1;
        d[1] = s.charAt(1) == '0' || Integer.valueOf(s.substring(0,2)) > 26 ? 1 : 2;
        for(int i = 2;i < s.length();i++) {
            if (s.charAt(i) == '0' ) {
                if(s.charAt(i-1) < '3' && s.charAt(i-1) > '0')
                    d[i] = d[i-2];
                else  {
                    System.out.println("有0种");
                    return;
                }
            } else {
                int val = Integer.valueOf(s.substring(i-1,i+1));
                d[i] = val > 26 ? d[i-1] : s.charAt(i-1) == '0' ? d[i-1] : (d[i-2] + d[i-1]);
            }

        }
        System.out.println("共有" + d[s.length()-1] + "种");
    }

    public int cal(String s) {
        int[] d = new int[s.length()];
        if (s.length() == 0 || s.length() == 1 ) {
            return 1;
        }

        d[0] = 1;
        d[1] = Integer.valueOf(s.substring(0,2)) > 26 ? 1 : 2;
        for(int i = 2;i < s.length();i++) {
            d[i] = d[i-1] + (Integer.valueOf(s.substring(i-1,i+1)) > 26 ? 0 : d[i-2]);
        }
        return d[s.length()-1];
    }

    /**
     * 不同的二叉搜索树
     *  G(n)表示n个数字一共有的个数
     *  F(i,n)表示以i为根的情况下一共有的个数
     *  由G(n) = 左 * 右(i<=n)，且有二叉搜索树的特性
     *  即F(i,n) = G(i-1) * G(n-i);
     *  G(n) = F(1,n) + F(2,n) + ... + F(n,n)
     *
     *  G(0) = 1,G(1) = 1,G(2) = 2
     *  G(3) = F(1,n) + F(2,n) + F(3,n) = G(0)*G(2) + G(1)*G(1) + G(2)*G(0)
     *  ...
     */
    @Test
    public void dynamic96() {
        int n = 3;
        if(n <= 1) {
            System.out.println("有1种");
            return;
        }

        if(n == 2) {
            System.out.println("有2种");
            return;
        }

        int[] count = new int[n+1];

        // 初始状态
        count[0] = count[1] = 1;
        count[2] = 2;


        for (int i = 3;i <= n;i++) {
            int tempCount = 0;

            for (int j = 1;j <= i;j++) {
                tempCount += count[j-1] * count[i-j];
            }
            count[i] = tempCount;
        }

        System.out.println("共有" + count[n] + "种二叉树");
    }

    /**
     * 不同的二叉树2
     * G(n)表示n个数字所有树的list
     *     F(i,n)表示以i为根的情况下的所有树的list
     *     由G(n) = 左 * 右(i<=n)，且有二叉搜索树的特性
     *     即F(i,n) = G(i-1) * G(n-i) 做笛卡尔积
     *     G(n) = F(1,n) + F(2,n) + ... + F(n,n) 加入一个list
     *
     *     G(0) = 1,G(1) = 1
     *     G(2) = F(1,2) + F(2,2) = G(0)*G(1) + G(1)*G(0)
     *     G(3) = F(1,n) + F(2,n) + F(3,n) = G(0)*G(2) + G(1)*G(1) + G(2)*G(0)
     *     ...
     */
    @Test
    public void dynamic95() {

        int n = 3;

        List<TreeNode> treeNodes = new ArrayList<>();

        treeNodes.add(new TreeNode(1));

        for(int i = 2;i <= n;i++) {
            // 对前一个tree[i-1]所有的最后加上数i
            // 添加根为i的数，即在根i的左边加上tree[i-1]中所有tree
            List<TreeNode> tempTrees = new ArrayList<>();
            for (TreeNode treeNode:treeNodes) {
                // 拷贝一份
                TreeNode tempNode = cloneTree(treeNode);

                // 进行根为i的操作
                TreeNode newTree = new TreeNode(i);
                newTree.left = treeNode;
                tempTrees.add(newTree);

                TreeNode temp = cloneTree(tempNode);
                TreeNode head = temp;

                int floor = 0;
                // 进行根为i-1的操作，需要讨论，因为i肯定出现在右子树上，但不确定是那哪一层
                // 循环到没有右孩子为止
                while (temp.right != null) {
                   floor ++;

                   TreeNode cur = new TreeNode(i);
                   cur.left = temp.right;
                   temp.right = cur;

                   tempTrees.add(head);

                   head = cloneTree(tempNode);
                   temp = head;
                   for (int k = 0;k < floor;k++) {
                       temp = temp.right;
                   }
                }
                temp.right = new TreeNode(i);
                tempTrees.add(head);
            }

            treeNodes = new ArrayList<>(tempTrees);

        }
    }

    // 注意树的正确拷贝方式
    public TreeNode cloneTree(TreeNode treeNode) {
        if(treeNode == null) {
            return null;
        }

        TreeNode newTreeNode = new TreeNode(treeNode.val);

        newTreeNode.left = cloneTree(treeNode.left);
        newTreeNode.right = cloneTree(treeNode.right);

        return newTreeNode;
    }

    /**
     * 戳气球
     */
    @Test
    public void leet_312() {
        // 回溯法 n!
        int[] nums = {3,1,5,8};
        // System.out.println(leet_312_1(nums, 0, 0));

        // 带缓存，回溯剪枝(自顶向下)
        // System.out.println(leet_312_2(nums));
        
        // DP(自底向上)
        System.out.println(leet_312_3(nums));
    }

    public int leet_312_1(int[] nums,int coins, int maxCoin) {
        if(nums.length == 0) {
            // System.out.println(coins);
            if(coins > maxCoin) {
                return coins;
            }
        }

        /**
         * 每次戳一个气球
         * 回溯到上一层时恢复戳破的气球
         */
        for (int i = 0; i < nums.length; i++) {
            int add = 0;
            if(i == 0) {
                add = nums[i] * (nums.length > 1 ? nums[i+1] : 1);
            } else if(i == nums.length - 1) {
                add = nums[i] * (nums.length > 1 ? nums[i-1] : 1);
            }
            else {
                add = nums[i-1] * nums[i] * nums[i+1];
            }
            coins += add;

            int[] newNums = new int[nums.length - 1];
            System.arraycopy(nums, 0, newNums, 0, i - 0);
            System.arraycopy(nums, i + 1, newNums, i, nums.length - 1 - i);
            maxCoin = leet_312_1(newNums, coins, maxCoin);

            // 回溯
            coins -= add;
        }
        return maxCoin;

    }


    // 带缓存，回溯剪枝
    public int leet_312_2(int[] nums) {
        // 处理数组，首位加1
        nums = manage(nums);

        int[][] cache = new int[nums.length][nums.length];

        // 回溯 + 缓存
        // 扩充1不影响计算
        return getMax(nums, 0, nums.length - 1, cache);
    }

    // 扩充数组边界
    public int[] manage(int[] nums) {
        int[] newNums = new int[nums.length + 2];
        newNums[0] = newNums[newNums.length - 1] = 1;

        System.arraycopy(nums, 0, newNums, 1, nums.length);
        return newNums;
    }

    // 回溯
    public int getMax(int[] nums,int begin,int end,int[][] cache) {
        /**
         * 注意下面for循环
         * 当begin,end紧随时
         * i = begin = end
         * 即返回0，只需计算戳破当前气球的收益
         */
        if(begin == end - 1) {
            return 0;
        }

        // 依据缓存
        if(cache[begin][end] != 0) {
            return cache[begin][end];
        }

        int max = 0;
        // begin .. i ..end
        // 这样分治最后肯定是剩余begin,i,end,
        for (int i = begin + 1; i < end; i++) {
            // 计算begin,end = (begin,i) + (i,end)
            int curMax = getMax(nums, begin, i, cache) +
                    getMax(nums, i, end, cache) + nums[begin] * nums[i] * nums[end];

            if(curMax > max) {
                max = curMax;
            }
        }
        cache[begin][end] = max;
        return max;
    }
    
    // DP循环
    public int leet_312_3(int[] nums){
        /**
         * 设k为i,j之间最后被扎破的气球
         * 缓存[i][j] = [i][k] + [k][j] + nums[i-1] * nums[j+1] + nums[k]
         * 三层循环：
         * 1. 从长度1 - n循环计算
         * 2. 每次从起始点开始计算长度为n的一段，[begin][begin+n]
         * 3. 设k为分割点，k从begin + 1开始到end - 1
         */
        int n = nums.length;

        // 扩充
        nums = manage(nums);
        int[][] dp = new int[nums.length + 2][nums.length + 2];

        // 这里长度1表示一个数，2表示两个数，所以到n
        for (int len = 1; len <= n; len++) {

            // 由于扩充后整体后移一位，就从1，n-i+1,  原本是0，n-i
            for (int begin = 1; begin <= n - len + 1; begin++) {

                // 长度为len,那么index对应是begin + len - 1
                int end = begin + len - 1;
                //
                for (int k = begin; k <= end; k++) {
                    dp[begin][end] = Math.max(dp[begin][k-1] + dp[k+1][end] +
                            nums[begin-1] * nums[k] * nums[end+1],dp[begin][end]);
                }
            }
        }

        return dp[1][n];
        
    }

    /**
     * 最大矩形
     */
    @Test
    public void leet_85() {
        /**
         * 1. 从上往下进行每一行的遍历；
         * 2. 用一个数组记录每一列的高度，当前节点为0时高度直接为0，若当前节点非0则+1；
         * 3. 对每一行计算最大矩形
         */
        char[][] nums = {
                {'1','0','1','0','0'},
                {'1','0','1','1','1'},
                {'1','1','1','1','1'},
                {'1','0','0','1','0'}};

        int[] heights = new int[nums[0].length];

        int maxArea = 0;

        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums[i].length; j++) {
                if(nums[i][j] == '1') {
                    heights[j] += 1;
                } else {
                    heights[j] = 0;
                }
            }

            maxArea = Math.max(maxArea, singleRec(heights));
        }

        System.out.println(maxArea);
    }

    public int singleRec(int[] heights) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);
        int maxArea = 0;

        for (int i = 0; i < heights.length; i++) {

            while (stack.peek() != -1 && heights[stack.peek()] > heights[i]) {
                int index = stack.poll();

                int width = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, width * heights[index]);
            }

            stack.push(i);
        }

        while (stack.peek() != -1) {
            int index = stack.poll();

            int width = heights.length - stack.peek() - 1;
            maxArea = Math.max(maxArea, width * heights[index]);
        }

        return maxArea;
    }

    /**
     * 打家劫舍
     */
    @Test
    public void leet_198() {
        int[] nums = {1,2,3,1};
        if(nums == null || nums.length == 0) {
            System.out.println(0);
        }

        /**
         * dp[i]:偷取到第i家的最大值
         * dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
         *
         * 节省空间可以只用两个变量存储
         */
        int preMax = 0;
        int curMax = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int temp = curMax;
            curMax = Math.max(preMax + nums[i], curMax);
            preMax = temp;
        }

        System.out.println(curMax);


    }



}
